home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / UNIXTOOL / GNU / PERL / PERL5SRC.ZIP / !Perl / c / regexec < prev    next >
Text File  |  1995-02-12  |  24KB  |  1,077 lines
  1. /*    regexec.c
  2.  */
  3.  
  4. /*
  5.  * "One Ring to rule them all, One Ring to find them..."
  6.  */
  7.  
  8. /* NOTE: this is derived from Henry Spencer's regexp code, and should not
  9.  * confused with the original package (see point 3 below).  Thanks, Henry!
  10.  */
  11.  
  12. /* Additional note: this code is very heavily munged from Henry's version
  13.  * in places.  In some spots I've traded clarity for efficiency, so don't
  14.  * blame Henry for some of the lack of readability.
  15.  */
  16.  
  17. /*SUPPRESS 112*/
  18. /*
  19.  * regcomp and regexec -- regsub and regerror are not used in perl
  20.  *
  21.  *    Copyright (c) 1986 by University of Toronto.
  22.  *    Written by Henry Spencer.  Not derived from licensed software.
  23.  *
  24.  *    Permission is granted to anyone to use this software for any
  25.  *    purpose on any computer system, and to redistribute it freely,
  26.  *    subject to the following restrictions:
  27.  *
  28.  *    1. The author is not responsible for the consequences of use of
  29.  *        this software, no matter how awful, even if they arise
  30.  *        from defects in it.
  31.  *
  32.  *    2. The origin of this software must not be misrepresented, either
  33.  *        by explicit claim or by omission.
  34.  *
  35.  *    3. Altered versions must be plainly marked as such, and must not
  36.  *        be misrepresented as being the original software.
  37.  *
  38.  ****    Alterations to Henry's code are...
  39.  ****
  40.  ****    Copyright (c) 1991-1994, Larry Wall
  41.  ****
  42.  ****    You may distribute under the terms of either the GNU General Public
  43.  ****    License or the Artistic License, as specified in the README file.
  44.  *
  45.  * Beware that some of this code is subtly aware of the way operator
  46.  * precedence is structured in regular expressions.  Serious changes in
  47.  * regular-expression syntax might require a total rethink.
  48.  */
  49. #include "EXTERN.h"
  50. #include "perl.h"
  51. #include "regcomp.h"
  52.  
  53. #ifndef STATIC
  54. #define    STATIC    static
  55. #endif
  56.  
  57. #ifdef DEBUGGING
  58. static I32 regnarrate = 0;
  59. static char* regprogram = 0;
  60. #endif
  61.  
  62. /* Current curly descriptor */
  63. typedef struct curcur CURCUR;
  64. struct curcur {
  65.     int        parenfloor;    /* how far back to strip paren data */
  66.     int        cur;        /* how many instances of scan we've matched */
  67.     int        min;        /* the minimal number of scans to match */
  68.     int        max;        /* the maximal number of scans to match */
  69.     int        minmod;        /* whether to work our way up or down */
  70.     char *    scan;        /* the thing to match */
  71.     char *    next;        /* what has to match after it */
  72.     char *    lastloc;    /* where we started matching this scan */
  73.     CURCUR *    oldcc;        /* current curly before we started this one */
  74. };
  75.  
  76. static CURCUR* regcc;
  77.  
  78. typedef I32 CHECKPOINT;
  79.  
  80. CHECKPOINT regcppush _((I32 parenfloor));
  81. char * regcppop _((void));
  82.  
  83. CHECKPOINT
  84. regcppush(parenfloor)
  85. I32 parenfloor;
  86. {
  87.     int retval = savestack_ix;
  88.     int i = (regsize - parenfloor) * 3;
  89.     int p;
  90.  
  91.     SSCHECK(i + 5);
  92.     for (p = regsize; p > parenfloor; p--) {
  93.     SSPUSHPTR(regendp[p]);
  94.     SSPUSHPTR(regstartp[p]);
  95.     SSPUSHINT(p);
  96.     }
  97.     SSPUSHINT(regsize);
  98.     SSPUSHINT(*reglastparen);
  99.     SSPUSHPTR(reginput);
  100.     SSPUSHINT(i + 3);
  101.     SSPUSHINT(SAVEt_REGCONTEXT);
  102.     return retval;
  103. }
  104.  
  105. char*
  106. regcppop()
  107. {
  108.     I32 i = SSPOPINT;
  109.     U32 paren = 0;
  110.     char *input;
  111.     char *tmps;
  112.     assert(i == SAVEt_REGCONTEXT);
  113.     i = SSPOPINT;
  114.     input = (char *) SSPOPPTR;
  115.     *reglastparen = SSPOPINT;
  116.     regsize = SSPOPINT;
  117.     for (i -= 3; i > 0; i -= 3) {
  118.     paren = (U32)SSPOPINT;
  119.     regstartp[paren] = (char *) SSPOPPTR;
  120.     tmps = (char*)SSPOPPTR;
  121.     if (paren <= *reglastparen)
  122.         regendp[paren] = tmps;
  123.     }
  124.     for (paren = *reglastparen + 1; paren <= regnpar; paren++) {
  125.     if (paren > regsize)
  126.         regstartp[paren] = Nullch;
  127.     regendp[paren] = Nullch;
  128.     }
  129.     return input;
  130. }
  131.  
  132. #define regcpblow(cp) leave_scope(cp)
  133.  
  134. /*
  135.  * regexec and friends
  136.  */
  137.  
  138. /*
  139.  * Forwards.
  140.  */
  141.  
  142. static I32 regmatch _((char *prog));
  143. static I32 regrepeat _((char *p, I32 max));
  144. static I32 regtry _((regexp *prog, char *startpos));
  145.  
  146. /*
  147.  - regexec - match a regexp against a string
  148.  */
  149. I32
  150. regexec(prog, stringarg, strend, strbeg, minend, screamer, safebase)
  151. register regexp *prog;
  152. char *stringarg;
  153. register char *strend;    /* pointer to null at end of string */
  154. char *strbeg;    /* real beginning of string */
  155. I32 minend;    /* end of match must be at least minend after stringarg */
  156. SV *screamer;
  157. I32 safebase;    /* no need to remember string in subbase */
  158. {
  159.     register char *s;
  160.     register I32 i;
  161.     register char *c;
  162.     register char *startpos = stringarg;
  163.     register I32 tmp;
  164.     I32 minlen = 0;        /* must match at least this many chars */
  165.     I32 dontbother = 0;    /* how many characters not to try at end */
  166.     CURCUR cc;
  167.  
  168.     cc.cur = 0;
  169.     regcc = &cc;
  170.  
  171. #ifdef DEBUGGING
  172.     regnarrate = debug & 512;
  173.     regprogram = prog->program;
  174. #endif
  175.  
  176.     /* Be paranoid... */
  177.     if (prog == NULL || startpos == NULL) {
  178.     croak("NULL regexp parameter");
  179.     return 0;
  180.     }
  181.  
  182.     if (startpos == strbeg)    /* is ^ valid at stringarg? */
  183.     regprev = '\n';
  184.     else {
  185.     regprev = stringarg[-1];
  186.     if (!multiline && regprev == '\n')
  187.         regprev = '\0';        /* force ^ to NOT match */
  188.     }
  189.     regprecomp = prog->precomp;
  190.     regnpar = prog->nparens;
  191.     /* Check validity of program. */
  192.     if (UCHARAT(prog->program) != MAGIC) {
  193.     FAIL("corrupted regexp program");
  194.     }
  195.  
  196.     if (prog->do_folding) {
  197.     i = strend - startpos;
  198.     New(1101,c,i+1,char);
  199.     Copy(startpos, c, i+1, char);
  200.     startpos = c;
  201.     strend = startpos + i;
  202.     for (s = startpos; s < strend; s++)
  203.         if (isUPPER(*s))
  204.         *s = toLOWER(*s);
  205.     }
  206.  
  207.     /* If there is a "must appear" string, look for it. */
  208.     s = startpos;
  209.     if (prog->regmust != Nullsv &&
  210.     (!(prog->reganch & ROPT_ANCH)
  211.      || (multiline && prog->regback >= 0)) )
  212.     {
  213.     if (stringarg == strbeg && screamer) {
  214.         if (screamfirst[BmRARE(prog->regmust)] >= 0)
  215.             s = screaminstr(screamer,prog->regmust);
  216.         else
  217.             s = Nullch;
  218.     }
  219.     else
  220.         s = fbm_instr((unsigned char*)s, (unsigned char*)strend,
  221.         prog->regmust);
  222.     if (!s) {
  223.         ++BmUSEFUL(prog->regmust);    /* hooray */
  224.         goto phooey;    /* not present */
  225.     }
  226.     else if (prog->regback >= 0) {
  227.         s -= prog->regback;
  228.         if (s < startpos)
  229.         s = startpos;
  230.         minlen = prog->regback + SvCUR(prog->regmust);
  231.     }
  232.     else if (!prog->naughty && --BmUSEFUL(prog->regmust) < 0) { /* boo */
  233.         SvREFCNT_dec(prog->regmust);
  234.         prog->regmust = Nullsv;    /* disable regmust */
  235.         s = startpos;
  236.     }
  237.     else {
  238.         s = startpos;
  239.         minlen = SvCUR(prog->regmust);
  240.     }
  241.     }
  242.  
  243.     /* Mark beginning of line for ^ . */
  244.     regbol = startpos;
  245.  
  246.     /* Mark end of line for $ (and such) */
  247.     regeol = strend;
  248.  
  249.     /* see how far we have to get to not match where we matched before */
  250.     regtill = startpos+minend;
  251.  
  252.     /* Simplest case:  anchored match need be tried only once. */
  253.     /*  [unless multiline is set] */
  254.     if (prog->reganch & ROPT_ANCH) {
  255.     if (regtry(prog, startpos))
  256.         goto got_it;
  257.     else if (multiline || (prog->reganch & ROPT_IMPLICIT)) {
  258.         if (minlen)
  259.         dontbother = minlen - 1;
  260.         strend -= dontbother;
  261.         /* for multiline we only have to try after newlines */
  262.         if (s > startpos)
  263.         s--;
  264.         while (s < strend) {
  265.         if (*s++ == '\n') {
  266.             if (s < strend && regtry(prog, s))
  267.             goto got_it;
  268.         }
  269.         }
  270.     }
  271.     goto phooey;
  272.     }
  273.  
  274.     /* Messy cases:  unanchored match. */
  275.     if (prog->regstart) {
  276.     if (prog->reganch & ROPT_SKIP) {  /* we have /x+whatever/ */
  277.         /* it must be a one character string */
  278.         i = SvPVX(prog->regstart)[0];
  279.         while (s < strend) {
  280.         if (*s == i) {
  281.             if (regtry(prog, s))
  282.             goto got_it;
  283.             s++;
  284.             while (s < strend && *s == i)
  285.             s++;
  286.         }
  287.         s++;
  288.         }
  289.     }
  290.     else if (SvPOK(prog->regstart) == 3) {
  291.         /* We know what string it must start with. */
  292.         while ((s = fbm_instr((unsigned char*)s,
  293.           (unsigned char*)strend, prog->regstart)) != NULL)
  294.         {
  295.         if (regtry(prog, s))
  296.             goto got_it;
  297.         s++;
  298.         }
  299.     }
  300.     else {
  301.         c = SvPVX(prog->regstart);
  302.         while ((s = ninstr(s, strend, c, c + SvCUR(prog->regstart))) != NULL)
  303.         {
  304.         if (regtry(prog, s))
  305.             goto got_it;
  306.         s++;
  307.         }
  308.     }
  309.     goto phooey;
  310.     }
  311.     /*SUPPRESS 560*/
  312.     if (c = prog->regstclass) {
  313.     I32 doevery = (prog->reganch & ROPT_SKIP) == 0;
  314.  
  315.     if (minlen)
  316.         dontbother = minlen - 1;
  317.     strend -= dontbother;    /* don't bother with what can't match */
  318.     tmp = 1;
  319.     /* We know what class it must start with. */
  320.     switch (OP(c)) {
  321.     case ANYOF:
  322.         c = OPERAND(c);
  323.         while (s < strend) {
  324.         i = UCHARAT(s);
  325.         if (!(c[i >> 3] & (1 << (i&7)))) {
  326.             if (tmp && regtry(prog, s))
  327.             goto got_it;
  328.             else
  329.             tmp = doevery;
  330.         }
  331.         else
  332.             tmp = 1;
  333.         s++;
  334.         }
  335.         break;
  336.     case BOUND:
  337.         if (minlen)
  338.         dontbother++,strend--;
  339.         if (s != startpos) {
  340.         i = s[-1];
  341.         tmp = isALNUM(i);
  342.         }
  343.         else
  344.         tmp = isALNUM(regprev);    /* assume not alphanumeric */
  345.         while (s < strend) {
  346.         i = *s;
  347.         if (tmp != isALNUM(i)) {
  348.             tmp = !tmp;
  349.             if (regtry(prog, s))
  350.             goto got_it;
  351.         }
  352.         s++;
  353.         }
  354.         if ((minlen || tmp) && regtry(prog,s))
  355.         goto got_it;
  356.         break;
  357.     case NBOUND:
  358.         if (minlen)
  359.         dontbother++,strend--;
  360.         if (s != startpos) {
  361.         i = s[-1];
  362.         tmp = isALNUM(i);
  363.         }
  364.         else
  365.         tmp = isALNUM(regprev);    /* assume not alphanumeric */
  366.         while (s < strend) {
  367.         i = *s;
  368.         if (tmp != isALNUM(i))
  369.             tmp = !tmp;
  370.         else if (regtry(prog, s))
  371.             goto got_it;
  372.         s++;
  373.         }
  374.         if ((minlen || !tmp) && regtry(prog,s))
  375.         goto got_it;
  376.         break;
  377.     case ALNUM:
  378.         while (s < strend) {
  379.         i = *s;
  380.         if (isALNUM(i)) {
  381.             if (tmp && regtry(prog, s))
  382.             goto got_it;
  383.             else
  384.             tmp = doevery;
  385.         }
  386.         else
  387.             tmp = 1;
  388.         s++;
  389.         }
  390.         break;
  391.     case NALNUM:
  392.         while (s < strend) {
  393.         i = *s;
  394.         if (!isALNUM(i)) {
  395.             if (tmp && regtry(prog, s))
  396.             goto got_it;
  397.             else
  398.             tmp = doevery;
  399.         }
  400.         else
  401.             tmp = 1;
  402.         s++;
  403.         }
  404.         break;
  405.     case SPACE:
  406.         while (s < strend) {
  407.         if (isSPACE(*s)) {
  408.             if (tmp && regtry(prog, s))
  409.             goto got_it;
  410.             else
  411.             tmp = doevery;
  412.         }
  413.         else
  414.             tmp = 1;
  415.         s++;
  416.         }
  417.         break;
  418.     case NSPACE:
  419.         while (s < strend) {
  420.         if (!isSPACE(*s)) {
  421.             if (tmp && regtry(prog, s))
  422.             goto got_it;
  423.             else
  424.             tmp = doevery;
  425.         }
  426.         else
  427.             tmp = 1;
  428.         s++;
  429.         }
  430.         break;
  431.     case DIGIT:
  432.         while (s < strend) {
  433.         if (isDIGIT(*s)) {
  434.             if (tmp && regtry(prog, s))
  435.             goto got_it;
  436.             else
  437.             tmp = doevery;
  438.         }
  439.         else
  440.             tmp = 1;
  441.         s++;
  442.         }
  443.         break;
  444.     case NDIGIT:
  445.         while (s < strend) {
  446.         if (!isDIGIT(*s)) {
  447.             if (tmp && regtry(prog, s))
  448.             goto got_it;
  449.             else
  450.             tmp = doevery;
  451.         }
  452.         else
  453.             tmp = 1;
  454.         s++;
  455.         }
  456.         break;
  457.     }
  458.     }
  459.     else {
  460.     if (minlen)
  461.         dontbother = minlen - 1;
  462.     strend -= dontbother;
  463.     /* We don't know much -- general case. */
  464.     do {
  465.         if (regtry(prog, s))
  466.         goto got_it;
  467.     } while (s++ < strend);
  468.     }
  469.  
  470.     /* Failure. */
  471.     goto phooey;
  472.  
  473. got_it:
  474.     strend += dontbother;    /* uncheat */
  475.     prog->subbeg = strbeg;
  476.     prog->subend = strend;
  477.     if ((!safebase && (prog->nparens || sawampersand)) || prog->do_folding) {
  478.     i = strend - startpos + (stringarg - strbeg);
  479.     if (safebase) {            /* no need for $digit later */
  480.         s = strbeg;
  481.         prog->subend = s+i;
  482.     }
  483.     else if (strbeg != prog->subbase) {
  484.         s = savepvn(strbeg,i);    /* so $digit will work later */
  485.         if (prog->subbase)
  486.         Safefree(prog->subbase);
  487.         prog->subbeg = prog->subbase = s;
  488.         prog->subend = s+i;
  489.     }
  490.     else {
  491.         prog->subbeg = s = prog->subbase;
  492.         prog->subend = s+i;
  493.     }
  494.     s += (stringarg - strbeg);
  495.     for (i = 0; i <= prog->nparens; i++) {
  496.         if (prog->endp[i]) {
  497.         prog->startp[i] = s + (prog->startp[i] - startpos);
  498.         prog->endp[i] = s + (prog->endp[i] - startpos);
  499.         }
  500.     }
  501.     if (prog->do_folding)
  502.         Safefree(startpos);
  503.     }
  504.     return 1;
  505.  
  506. phooey:
  507.     if (prog->do_folding)
  508.     Safefree(startpos);
  509.     return 0;
  510. }
  511.  
  512. /*
  513.  - regtry - try match at specific point
  514.  */
  515. static I32            /* 0 failure, 1 success */
  516. regtry(prog, startpos)
  517. regexp *prog;
  518. char *startpos;
  519. {
  520.     register I32 i;
  521.     register char **sp;
  522.     register char **ep;
  523.  
  524.     reginput = startpos;
  525.     regstartp = prog->startp;
  526.     regendp = prog->endp;
  527.     reglastparen = &prog->lastparen;
  528.     prog->lastparen = 0;
  529.     regsize = 0;
  530.  
  531.     sp = prog->startp;
  532.     ep = prog->endp;
  533.     if (prog->nparens) {
  534.     for (i = prog->nparens; i >= 0; i--) {
  535.         *sp++ = NULL;
  536.         *ep++ = NULL;
  537.     }
  538.     }
  539.     if (regmatch(prog->program + 1) && reginput >= regtill) {
  540.     prog->startp[0] = startpos;
  541.     prog->endp[0] = reginput;
  542.     return 1;
  543.     }
  544.     else
  545.     return 0;
  546. }
  547.  
  548. /*
  549.  - regmatch - main matching routine
  550.  *
  551.  * Conceptually the strategy is simple:  check to see whether the current
  552.  * node matches, call self recursively to see whether the rest matches,
  553.  * and then act accordingly.  In practice we make some effort to avoid
  554.  * recursion, in particular by going through "ordinary" nodes (that don't
  555.  * need to know whether the rest of the match failed) by a loop instead of
  556.  * by recursion.
  557.  */
  558. /* [lwall] I've hoisted the register declarations to the outer block in order to
  559.  * maybe save a little bit of pushing and popping on the stack.  It also takes
  560.  * advantage of machines that use a register save mask on subroutine entry.
  561.  */
  562. static I32            /* 0 failure, 1 success */
  563. regmatch(prog)
  564. char *prog;
  565. {
  566.     register char *scan;    /* Current node. */
  567.     char *next;            /* Next node. */
  568.     register I32 nextchar;
  569.     register I32 n;        /* no or next */
  570.     register I32 ln;        /* len or last */
  571.     register char *s;        /* operand or save */
  572.     register char *locinput = reginput;
  573.     int minmod = 0;
  574.  
  575.     nextchar = *locinput;
  576.     scan = prog;
  577.     while (scan != NULL) {
  578. #ifdef DEBUGGING
  579.     if (regnarrate)
  580.         fprintf(stderr, "%2d%-8.8s\t<%.10s>\n",
  581.         scan - regprogram, regprop(scan), locinput);
  582. #endif
  583.  
  584. #ifdef REGALIGN
  585.     next = scan + NEXT(scan);
  586.     if (next == scan)
  587.         next = NULL;
  588. #else
  589.     next = regnext(scan);
  590. #endif
  591.  
  592.     switch (OP(scan)) {
  593.     case BOL:
  594.         if (locinput == regbol
  595.         ? regprev == '\n'
  596.         : ((nextchar || locinput < regeol) && locinput[-1] == '\n') )
  597.         {
  598.         /* regtill = regbol; */
  599.         break;
  600.         }
  601.         return 0;
  602.     case MBOL:
  603.         if (locinput == regbol
  604.         ? regprev == '\n'
  605.         : ((nextchar || locinput < regeol) && locinput[-1] == '\n') )
  606.         {
  607.         break;
  608.         }
  609.         return 0;
  610.     case SBOL:
  611.         if (locinput == regbol && regprev == '\n')
  612.         break;
  613.         return 0;
  614.     case GBOL:
  615.         if (locinput == regbol)
  616.         break;
  617.         return 0;
  618.     case EOL:
  619.         if (multiline)
  620.         goto meol;
  621.         else
  622.         goto seol;
  623.     case MEOL:
  624.       meol:
  625.         if ((nextchar || locinput < regeol) && nextchar != '\n')
  626.         return 0;
  627.         break;
  628.     case SEOL:
  629.       seol:
  630.         if ((nextchar || locinput < regeol) && nextchar != '\n')
  631.         return 0;
  632.         if (regeol - locinput > 1)
  633.         return 0;
  634.         break;
  635.     case SANY:
  636.         if (!nextchar && locinput >= regeol)
  637.         return 0;
  638.         nextchar = *++locinput;
  639.         break;
  640.     case ANY:
  641.         if (!nextchar && locinput >= regeol || nextchar == '\n')
  642.         return 0;
  643.         nextchar = *++locinput;
  644.         break;
  645.     case EXACTLY:
  646.         s = OPERAND(scan);
  647.         ln = *s++;
  648.         /* Inline the first character, for speed. */
  649.         if (*s != nextchar)
  650.         return 0;
  651.         if (regeol - locinput < ln)
  652.         return 0;
  653.         if (ln > 1 && bcmp(s, locinput, ln) != 0)
  654.         return 0;
  655.         locinput += ln;
  656.         nextchar = *locinput;
  657.         break;
  658.     case ANYOF:
  659.         s = OPERAND(scan);
  660.         if (nextchar < 0)
  661.         nextchar = UCHARAT(locinput);
  662.         if (s[nextchar >> 3] & (1 << (nextchar&7)))
  663.         return 0;
  664.         if (!nextchar && locinput >= regeol)
  665.         return 0;
  666.         nextchar = *++locinput;
  667.         break;
  668.     case ALNUM:
  669.         if (!nextchar)
  670.         return 0;
  671.         if (!isALNUM(nextchar))
  672.         return 0;
  673.         nextchar = *++locinput;
  674.         break;
  675.     case NALNUM:
  676.         if (!nextchar && locinput >= regeol)
  677.         return 0;
  678.         if (isALNUM(nextchar))
  679.         return 0;
  680.         nextchar = *++locinput;
  681.         break;
  682.     case NBOUND:
  683.     case BOUND:
  684.         if (locinput == regbol)    /* was last char in word? */
  685.         ln = isALNUM(regprev);
  686.         else 
  687.         ln = isALNUM(locinput[-1]);
  688.         n = isALNUM(nextchar); /* is next char in word? */
  689.         if ((ln == n) == (OP(scan) == BOUND))
  690.         return 0;
  691.         break;
  692.     case SPACE:
  693.         if (!nextchar && locinput >= regeol)
  694.         return 0;
  695.         if (!isSPACE(nextchar))
  696.         return 0;
  697.         nextchar = *++locinput;
  698.         break;
  699.     case NSPACE:
  700.         if (!nextchar)
  701.         return 0;
  702.         if (isSPACE(nextchar))
  703.         return 0;
  704.         nextchar = *++locinput;
  705.         break;
  706.     case DIGIT:
  707.         if (!isDIGIT(nextchar))
  708.         return 0;
  709.         nextchar = *++locinput;
  710.         break;
  711.     case NDIGIT:
  712.         if (!nextchar && locinput >= regeol)
  713.         return 0;
  714.         if (isDIGIT(nextchar))
  715.         return 0;
  716.         nextchar = *++locinput;
  717.         break;
  718.     case REF:
  719.         n = ARG1(scan);  /* which paren pair */
  720.         s = regstartp[n];
  721.         if (!s)
  722.         return 0;
  723.         if (!regendp[n])
  724.         return 0;
  725.         if (s == regendp[n])
  726.         break;
  727.         /* Inline the first character, for speed. */
  728.         if (*s != nextchar)
  729.         return 0;
  730.         ln = regendp[n] - s;
  731.         if (locinput + ln > regeol)
  732.         return 0;
  733.         if (ln > 1 && bcmp(s, locinput, ln) != 0)
  734.         return 0;
  735.         locinput += ln;
  736.         nextchar = *locinput;
  737.         break;
  738.  
  739.     case NOTHING:
  740.         break;
  741.     case BACK:
  742.         break;
  743.     case OPEN:
  744.         n = ARG1(scan);  /* which paren pair */
  745.         regstartp[n] = locinput;
  746.         if (n > regsize)
  747.         regsize = n;
  748.         break;
  749.     case CLOSE:
  750.         n = ARG1(scan);  /* which paren pair */
  751.         regendp[n] = locinput;
  752.         if (n > *reglastparen)
  753.         *reglastparen = n;
  754.         break;
  755.     case CURLYX: {
  756.         CURCUR cc;
  757.         CHECKPOINT cp = savestack_ix;
  758.         cc.oldcc = regcc;
  759.         regcc = &cc;
  760.         cc.parenfloor = *reglastparen;
  761.         cc.cur = -1;
  762.         cc.min = ARG1(scan);
  763.         cc.max  = ARG2(scan);
  764.         cc.scan = NEXTOPER(scan) + 4;
  765.         cc.next = next;
  766.         cc.minmod = minmod;
  767.         cc.lastloc = 0;
  768.         reginput = locinput;
  769.         n = regmatch(PREVOPER(next));    /* start on the WHILEM */
  770.         regcpblow(cp);
  771.         regcc = cc.oldcc;
  772.         return n;
  773.         }
  774.         /* NOT REACHED */
  775.     case WHILEM: {
  776.         /*
  777.          * This is really hard to understand, because after we match
  778.          * what we're trying to match, we must make sure the rest of
  779.          * the RE is going to match for sure, and to do that we have
  780.          * to go back UP the parse tree by recursing ever deeper.  And
  781.          * if it fails, we have to reset our parent's current state
  782.          * that we can try again after backing off.
  783.          */
  784.  
  785.         CURCUR* cc = regcc;
  786.         n = cc->cur + 1;
  787.         reginput = locinput;
  788.  
  789.         /* If degenerate scan matches "", assume scan done. */
  790.  
  791.         if (locinput == cc->lastloc) {
  792.             regcc = cc->oldcc;
  793.             ln = regcc->cur;
  794.             if (regmatch(cc->next))
  795.             return TRUE;
  796.             regcc->cur = ln;
  797.             regcc = cc;
  798.             return FALSE;
  799.         }
  800.  
  801.         /* First just match a string of min scans. */
  802.  
  803.         if (n < cc->min) {
  804.             cc->cur = n;
  805.             cc->lastloc = locinput;
  806.             return regmatch(cc->scan);
  807.         }
  808.  
  809.         /* Prefer next over scan for minimal matching. */
  810.  
  811.         if (cc->minmod) {
  812.             regcc = cc->oldcc;
  813.             ln = regcc->cur;
  814.             if (regmatch(cc->next))
  815.             return TRUE;    /* All done. */
  816.             regcc->cur = ln;
  817.             regcc = cc;
  818.  
  819.             if (n >= cc->max)    /* Maximum greed exceeded? */
  820.             return FALSE;
  821.  
  822.             /* Try scanning more and see if it helps. */
  823.             reginput = locinput;
  824.             cc->cur = n;
  825.             cc->lastloc = locinput;
  826.             return regmatch(cc->scan);
  827.         }
  828.  
  829.         /* Prefer scan over next for maximal matching. */
  830.  
  831.         if (n < cc->max) {    /* More greed allowed? */
  832.             regcppush(cc->parenfloor);
  833.             cc->cur = n;
  834.             cc->lastloc = locinput;
  835.             if (regmatch(cc->scan))
  836.             return TRUE;
  837.             regcppop();        /* Restore some previous $<digit>s? */
  838.             reginput = locinput;
  839.         }
  840.  
  841.         /* Failed deeper matches of scan, so see if this one works. */
  842.         regcc = cc->oldcc;
  843.         ln = regcc->cur;
  844.         if (regmatch(cc->next))
  845.             return TRUE;
  846.         regcc->cur = ln;
  847.         regcc = cc;
  848.         return FALSE;
  849.         }
  850.         /* NOT REACHED */
  851.     case BRANCH: {
  852.         if (OP(next) != BRANCH)      /* No choice. */
  853.             next = NEXTOPER(scan);/* Avoid recursion. */
  854.         else {
  855.             int lastparen = *reglastparen;
  856.             do {
  857.             reginput = locinput;
  858.             if (regmatch(NEXTOPER(scan)))
  859.                 return 1;
  860.             for (n = *reglastparen; n > lastparen; n--)
  861.                 regendp[n] = 0;
  862.             *reglastparen = n;
  863.                 
  864. #ifdef REGALIGN
  865.             /*SUPPRESS 560*/
  866.             if (n = NEXT(scan))
  867.                 scan += n;
  868.             else
  869.                 scan = NULL;
  870. #else
  871.             scan = regnext(scan);
  872. #endif
  873.             } while (scan != NULL && OP(scan) == BRANCH);
  874.             return 0;
  875.             /* NOTREACHED */
  876.         }
  877.         }
  878.         break;
  879.     case MINMOD:
  880.         minmod = 1;
  881.         break;
  882.     case CURLY:
  883.         ln = ARG1(scan);  /* min to match */
  884.         n  = ARG2(scan);  /* max to match */
  885.         scan = NEXTOPER(scan) + 4;
  886.         goto repeat;
  887.     case STAR:
  888.         ln = 0;
  889.         n = 32767;
  890.         scan = NEXTOPER(scan);
  891.         goto repeat;
  892.     case PLUS:
  893.         /*
  894.         * Lookahead to avoid useless match attempts
  895.         * when we know what character comes next.
  896.         */
  897.         ln = 1;
  898.         n = 32767;
  899.         scan = NEXTOPER(scan);
  900.       repeat:
  901.         if (OP(next) == EXACTLY)
  902.         nextchar = *(OPERAND(next)+1);
  903.         else
  904.         nextchar = -1000;
  905.         reginput = locinput;
  906.         if (minmod) {
  907.         minmod = 0;
  908.         if (ln && regrepeat(scan, ln) < ln)
  909.             return 0;
  910.         while (n >= ln) {
  911.             /* If it could work, try it. */
  912.             if (nextchar == -1000 || *reginput == nextchar)
  913.             if (regmatch(next))
  914.                 return 1;
  915.             /* Couldn't or didn't -- back up. */
  916.             reginput = locinput + ln;
  917.             if (regrepeat(scan, 1)) {
  918.             ln++;
  919.             reginput = locinput + ln;
  920.             }
  921.             else
  922.             return 0;
  923.         }
  924.         }
  925.         else {
  926.         n = regrepeat(scan, n);
  927.         if (ln < n && regkind[(U8)OP(next)] == EOL &&
  928.             (!multiline || OP(next) == SEOL))
  929.             ln = n;            /* why back off? */
  930.         while (n >= ln) {
  931.             /* If it could work, try it. */
  932.             if (nextchar == -1000 || *reginput == nextchar)
  933.             if (regmatch(next))
  934.                 return 1;
  935.             /* Couldn't or didn't -- back up. */
  936.             n--;
  937.             reginput = locinput + n;
  938.         }
  939.         }
  940.         return 0;
  941.     case SUCCEED:
  942.     case END:
  943.         reginput = locinput;    /* put where regtry can find it */
  944.         return 1;            /* Success! */
  945.     case IFMATCH:
  946.         reginput = locinput;
  947.         scan = NEXTOPER(scan);
  948.         if (!regmatch(scan))
  949.         return 0;
  950.         break;
  951.     case UNLESSM:
  952.         reginput = locinput;
  953.         scan = NEXTOPER(scan);
  954.         if (regmatch(scan))
  955.         return 0;
  956.         break;
  957.     default:
  958.         fprintf(stderr, "%x %d\n",(unsigned)scan,scan[1]);
  959.         FAIL("regexp memory corruption");
  960.     }
  961.     scan = next;
  962.     }
  963.  
  964.     /*
  965.     * We get here only if there's trouble -- normally "case END" is
  966.     * the terminating point.
  967.     */
  968.     FAIL("corrupted regexp pointers");
  969.     /*NOTREACHED*/
  970.     return 0;
  971. }
  972.  
  973. /*
  974.  - regrepeat - repeatedly match something simple, report how many
  975.  */
  976. /*
  977.  * [This routine now assumes that it will only match on things of length 1.
  978.  * That was true before, but now we assume scan - reginput is the count,
  979.  * rather than incrementing count on every character.]
  980.  */
  981. static I32
  982. regrepeat(p, max)
  983. char *p;
  984. I32 max;
  985. {
  986.     register char *scan;
  987.     register char *opnd;
  988.     register I32 c;
  989.     register char *loceol = regeol;
  990.  
  991.     scan = reginput;
  992.     if (max != 32767 && max < loceol - scan)
  993.       loceol = scan + max;
  994.     opnd = OPERAND(p);
  995.     switch (OP(p)) {
  996.     case ANY:
  997.     while (scan < loceol && *scan != '\n')
  998.         scan++;
  999.     break;
  1000.     case SANY:
  1001.     scan = loceol;
  1002.     break;
  1003.     case EXACTLY:        /* length of string is 1 */
  1004.     opnd++;
  1005.     while (scan < loceol && *opnd == *scan)
  1006.         scan++;
  1007.     break;
  1008.     case ANYOF:
  1009.     c = UCHARAT(scan);
  1010.     while (scan < loceol && !(opnd[c >> 3] & (1 << (c & 7)))) {
  1011.         scan++;
  1012.         c = UCHARAT(scan);
  1013.     }
  1014.     break;
  1015.     case ALNUM:
  1016.     while (scan < loceol && isALNUM(*scan))
  1017.         scan++;
  1018.     break;
  1019.     case NALNUM:
  1020.     while (scan < loceol && !isALNUM(*scan))
  1021.         scan++;
  1022.     break;
  1023.     case SPACE:
  1024.     while (scan < loceol && isSPACE(*scan))
  1025.         scan++;
  1026.     break;
  1027.     case NSPACE:
  1028.     while (scan < loceol && !isSPACE(*scan))
  1029.         scan++;
  1030.     break;
  1031.     case DIGIT:
  1032.     while (scan < loceol && isDIGIT(*scan))
  1033.         scan++;
  1034.     break;
  1035.     case NDIGIT:
  1036.     while (scan < loceol && !isDIGIT(*scan))
  1037.         scan++;
  1038.     break;
  1039.     default:        /* Called on something of 0 width. */
  1040.     break;        /* So match right here or not at all. */
  1041.     }
  1042.  
  1043.     c = scan - reginput;
  1044.     reginput = scan;
  1045.  
  1046.     return(c);
  1047. }
  1048.  
  1049. /*
  1050.  - regnext - dig the "next" pointer out of a node
  1051.  *
  1052.  * [Note, when REGALIGN is defined there are two places in regmatch()
  1053.  * that bypass this code for speed.]
  1054.  */
  1055. char *
  1056. regnext(p)
  1057. register char *p;
  1058. {
  1059.     register I32 offset;
  1060.  
  1061.     if (p == ®dummy)
  1062.     return(NULL);
  1063.  
  1064.     offset = NEXT(p);
  1065.     if (offset == 0)
  1066.     return(NULL);
  1067.  
  1068. #ifdef REGALIGN
  1069.     return(p+offset);
  1070. #else
  1071.     if (OP(p) == BACK)
  1072.     return(p-offset);
  1073.     else
  1074.     return(p+offset);
  1075. #endif
  1076. }
  1077.